150E - Freezing with Style - CodeForces Solution

// Author: XZC(L_Wave)
// Language: Cpp/G++14
// Problem: E. Freezing with Style
// Contest: Codeforces - Codeforces Round 107 (Div. 1)
// URL: https://codeforces.com/contest/150/problem/E
// Memory Limit: 256 MB
// Time Limit: 7000 ms
// Create Time: not 2023-07-12 19:38:33, but 1926-08-17 11:45:14
//
// Powered by CP Editor (https://cpeditor.org)

// Congratulations to gjr who becomes the second 2022-junior grandmaster!
// Congratulations to qjm who becomes grandmaster again!
// Congratulations to csy who goes on the "top rated" board again!
// What a magic contest round 884 is!

//#pragma GCC optimize("Ofast", "inline")
#include <bits/stdc++.h>
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rpp(i, n) for (int i = 1; i <= (int)(n); i++)
#define Dpp(i, n) for (int i = (int)n; i; i--)
#define Frr(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define Tc    \
	int T;    \
	cin >> T; \
	while (T--)
#define Eps 1e-7
#define Pinf 0x3f3f3f3f
#define Ninf 0xcfcfcfcf
#define Mem0(Cont) memset(Cont, 0, sizeof(Cont))
#define MemP(Cont) memset(Cont, 0x3f, sizeof(Cont))
#define MemN(Cont) memset(Cont, 0xcf, sizeof(Cont))
#define endl '\n'
// #define int long long
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define yes cout << "yes\n"
#define no cout << "no\n"
#define pjj pair<int, int>
#define ff first
#define ss second
//#define Files
using namespace std;

template<typename T>
inline void Print(T x, char ed = '\n') {
	cout << x << ed;
}
template<typename T>
inline void Exit(T x, int cd = 0) {
	cout << x << endl;
	exit(cd);
}
template<typename T>
inline bool CheckMax(T& x, T y) {
	if (x < y) {
		x = y;
		return 1;
	} else
		return 0;
}
template<typename T>
inline bool CheckMin(T& x, T y) {
	if (y < x) {
		x = y;
		return 1;
	} else
		return 0;
}
inline void Print_if(bool sth, string s1 = "Yes", string s2 = "No") {
	if (sth)
		cout << s1 << endl;
	else
		cout << s2 << endl;
}

constexpr int N = 114514;

// Variables
bool vis[N];
int n, L, R, res, resU, resV, maxd[N], toW[N];
vector<int> son[N];

// Graph V
struct Edge {
	int v, num, w, nxt;
} E[N << 1];
int head[N], tot;
void add(int u, int v, int w) {
	E[++tot] = {v, w, 0, head[u]};
	head[u] = tot;
}

// Value V
struct Value {
	int u, dis;
	friend bool operator<(Value v1, Value v2) { return v1.dis < v2.dis; }
} in[N], by[N];
constexpr size_t valsz = sizeof(in[0]);

// Prework V
void init() {
	MemN(by);
	Mem0(vis);
}
void refill(int mid) { Rpp(i, tot) E[i].w = (E[i].num >= mid) ? 1 : -1; }

// Calculate depth & distance V
void dfs_val(int u, int p, int from, int dep, int dis) {
	if (dep > R) return;
	if (dep >= L && dis >= 0) {
		res = 0;
		resU = from;
		resV = u;
		return;
	}
	CheckMax(in[dep], {u, dis});
	for (int i = head[u]; i; i = E[i].nxt)
		if (E[i].v != p && !vis[E[i].v]) dfs_val(E[i].v, u, from, dep + 1, dis + E[i].w);
}

// Maximum depth (answer while building the order) V
void dfs_dep(int u, int p) {
	maxd[u] = 1;
	for (int i = head[u]; i; i = E[i].nxt)
		if (E[i].v != p && !vis[E[i].v]) {
			dfs_dep(E[i].v, u);
			CheckMax(maxd[u], maxd[E[i].v] + 1);
		}
}

// Centroid V
int calc_size(int u, int p) {
	int res = 1;
	for (int i = head[u]; i; i = E[i].nxt) {
		int v = E[i].v;
		if (v == p) continue;
		if (vis[v]) continue;
		res += calc_size(v, u);
	}
	return res;
}
int calc_centre(int u, int p, int all, int& res, int& psz) {
	int sz = 1, mssz = Ninf;
	for (int i = head[u]; i; i = E[i].nxt) {
		int v = E[i].v;
		if (v == p) continue;
		if (vis[v]) continue;
		int sonsz = calc_centre(v, u, all, res, psz);
		sz += sonsz;
		CheckMax(mssz, sonsz);
	}
	CheckMax(mssz, all - sz);
	if (CheckMin(psz, mssz)) res = u;
	return sz;
}
int centre(int u) {
	int psz = Pinf, res = 0, all = calc_size(u, 0);
	calc_centre(u, 0, all, res, psz);
	return res;
}

// Caluculate the answer
void build(int u) {
	son[u].clear();
	son[u].push_back(0);
	for (int i = head[u]; i; i = E[i].nxt) {
		if (vis[E[i].v]) continue;
		dfs_dep(E[i].v, u);
		son[u].push_back(E[i].v);
	}
	sort(son[u].begin(), son[u].end(), [](int x, int y) { return maxd[x] < maxd[y]; });
}
void calc(int u) {
	memset(by, 0xcf, valsz * (maxd[u] + 1));
	for (int i = head[u]; i; i = E[i].nxt) {
		if (vis[E[i].v]) continue;
		toW[E[i].v] = E[i].w;
		// cout << '#' << E[i].v << ' ' << E[i].w << endl;
	}
	build(u);
	int m = son[u].size() - 1;
	// cout << "&" << u << endl;
	Rpp(i, m) {
		int v = son[u][i];
		memset(in, 0xcf, valsz * (maxd[v] + 2));
		dfs_val(v, u, u, 1, toW[v]);
		// cout << '$' << u << ' ' << v << ' ' << res << ' ' << toW[v] << endl;
		if (res >= 0) return;
		deque<int> Q;
		Frr(j, max(1, L - maxd[v]), min(R - maxd[v], maxd[son[u][i - 1]])) {
			while (Q.size() && by[Q.back()] < by[j]) Q.pop_back();
			Q.push_back(j);
		}
		// if (u == 4) cout << v << '*' << maxd[v] << endl;
		Dpp(j, min(maxd[v], R)) {
			while (Q.size() && Q.front() + j < L) Q.pop_front();
			if (R - j <= maxd[son[u][i - 1]]) {
				while (Q.size() && by[Q.back()] < by[R - j]) Q.pop_back();
				Q.push_back(R - j);
			}
			int d = !Q.size() ? Ninf : by[Q.front()].dis;
			if (d + in[j].dis >= 0) {
				res = d + in[j].dis;
				resU = in[j].u;
				resV = by[Q.front()].u;
				return;
			}
		}
		Rpp(j, maxd[v]) CheckMax(by[j], in[j]);
	}
}

// Vertex D&C
void div_con(int u) {
	// cout << '%' << u << endl;
	vis[u] = 1;
	calc(u);
	for (int i = head[u]; i && res < 0; i = E[i].nxt) {
		if (!vis[E[i].v]) div_con(centre(E[i].v));
	}
}

// Binary Search
bool check(int mid) {
	// cout << mid << endl;
	init();
	refill(mid);
	res = Ninf;
	resU = 0;
	resV = 0;
	div_con(centre(1));
	// if (res >= 0) cout << mid << ' ' << res << endl;
	return res >= 0;
}
void solve() {
	int minw = Pinf, maxw = Ninf;
	Rpp(i, tot) CheckMin(minw, E[i].num);
	Rpp(i, tot) CheckMax(maxw, E[i].num);
	int lo = minw, hi = maxw, mi, outU = 0, outV = 0;
	while (lo <= hi) {
		mi = (lo + hi) >> 1;
		if (check(mi)) {
			outU = resU;
			outV = resV;
			lo = mi + 1;
		} else
			hi = mi - 1;
	}
	cout << outU << ' ' << outV << endl;
}

// Read
void read() {
	cin >> n >> L >> R;
	Rpp(i, n - 1) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
}

signed main() {
#ifdef Files
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	ios_base ::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	read();
	solve();

	return 0;
}

/*
 *	things to check
 *	1.  int overflow or long long memory need
 *	2.  recursion/array/binary search/dp/loop bounds
 *	3.  precision
 *	4.  special cases(n=1,bounds)
 *	5.  delete debug statements
 *	6.  initialize(especially multi-tests)
 *	7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
 *	8.  keep it simple and stupid
 *	9.  do not delete, use // instead
 *	10. operator priority
 *	11. is there anything extra to output?
 *	12. THINK TWICE CODE ONCE, THINK ONCE DEBUG FOREVER
 *	13. submit ONCE, AC once. submit twice, WA forever
 *	14. calm down and you'll get good rank
 *	15. even a bit wrong scores zero
 *	16. ...
 **/

/*
 *	something to think about
 *	1. greedy? dp? searching? dp with matrix/ segment tree? binary search? ...?
 *	2. If it is difficult, why not the opposite?
 **/